package datastruct;

import org.junit.Test;

import java.util.*;

public class LFUCache460 {
    @Test
    public void test() {
        LFUCache460 lFUCache = new LFUCache460();
        lFUCache.init(2);
        lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
        lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        System.out.format("lFUCache.get(1)=%d\n", lFUCache.get(1));      // 返回 1
        // cache=[1,2], cnt(2)=1, cnt(1)=2
        lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        // cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.format("lFUCache.get(2)=%d\n", lFUCache.get(2));      // 返回 -1（未找到）
        System.out.format("lFUCache.get(3)=%d\n", lFUCache.get(3));      // 返回 3
        // cache=[3,1], cnt(3)=2, cnt(1)=2
        lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        // cache=[4,3], cnt(4)=1, cnt(3)=2
        System.out.format("lFUCache.get(1)=%d\n", lFUCache.get(1));      // 返回 -1（未找到）
        System.out.format("lFUCache.get(3)=%d\n", lFUCache.get(3));      // 返回 3
        // cache=[3,4], cnt(4)=1, cnt(3)=3
        System.out.format("lFUCache.get(4)=%d\n", lFUCache.get(4));      // 返回 4
        // cache=[3,4], cnt(4)=2, cnt(3)=3
    }

    public static class Node {
        public Integer key;
        public Integer value;
        public int freq;
        public Node next;
        public Node prev;

        public Node(Integer key, Integer value, Node next, Node prev) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.prev = prev;
            this.freq = 0;
        }
    }

    public static class List {
        Node head;
        Node tail;

        public List() {
            this.head = new Node(null, null, null, null);
            this.tail = new Node(null, null, null, null);
            this.head.next = tail;
            this.tail.prev = head;
        }

        public boolean isEmpty() {
            return head.next == tail;
        }

        public void addFirst(Node node) {
            Node next = head.next;

            node.prev = head;
            node.next = next;

            next.prev = node;
            head.next = node;
        }

        public void removeNode(Node node) {
            if (node == head || node == tail) {
                return;
            }
            Node next = node.next;
            Node prev = node.prev;

            next.prev = prev;
            prev.next = next;

            // clear links
            node.next = null;
            node.prev = null;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            String sep = "";
            Node curr = head;
            while ((curr = curr.next) != tail) {
                sb.append(sep);
                sb.append(curr.value);
                sep = ", ";
            }
            sb.append("]");
            return sb.toString();
        }
    }

    int capacity;
    Map<Integer, Node> map;
    NavigableMap<Integer, List> freqListMap;

    public LFUCache460() {
    }

    public void init(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
        this.freqListMap = new TreeMap<>();
    }

//    public LFUCache(int capacity) {
//        init(capacity);
//    }

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            List list = freqListMap.get(node.freq);
            list.removeNode(node);
            if (list.isEmpty()) {
                freqListMap.remove(node.freq);
            }

            node.freq++;
            list = freqListMap.computeIfAbsent(node.freq, freq -> new List());
            list.addFirst(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            List list = freqListMap.get(node.freq);
            list.removeNode(node);
            if (list.isEmpty()) {
                freqListMap.remove(node.freq);
            }

            node.freq++;
            list = freqListMap.computeIfAbsent(node.freq, freq -> new List());
            list.addFirst(node);
        } else {
            // 注意, capacity可能为0
            if (capacity == 0) {
                return;
            }
            // 注意, 新插入的freq=1不能马上删. 因此要先删再插.
            if (map.size()+1 > capacity) {
                removeLeastFreqNode();
            }

            node = new Node(key, value, null, null);
            node.freq = 1;

            map.put(key, node);

            List list = freqListMap.computeIfAbsent(node.freq, freq -> new List());
            list.addFirst(node);
        }
    }

    public void removeLeastFreqNode() {
        Map.Entry<Integer, List> entry = freqListMap.firstEntry();

        List list = entry.getValue();
        map.remove(list.tail.prev.key);
        list.removeNode(list.tail.prev);

        if (list.isEmpty()) {
            freqListMap.remove(entry.getKey());
        }
    }
}
